package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
	
	private List<Integer> list;
	private int nextIdx = 0;
	
    public BSTIterator(TreeNode root) {
		list = new ArrayList<Integer>();
		TreeNode cur = root;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				list.add(cur.val);
				cur = cur.right;
			}
		}
    }
    
    /** @return the next smallest number */
    public int next() {
    	Integer val = list.get(nextIdx);
		nextIdx++;
		return val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
		return nextIdx < list.size();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */